An Internet service provider may seek to monitor the performance of customer Internet Protocol (“IP”) traffic within the service provider's network. For example, the service provider may seek to measure unidirectional reachability, packet loss rate, and packet delay along edge-to-edge paths followed by customer traffic. One proposed way to monitor IP traffic is by deploying two monitors for each edge router in the network. Each of these monitors may be connected to multiple edge routers. Thus, each monitor may monitor more than one edge router.
A content provider may seek to provide redundant content servers for each customer in a network in case one of the data stores fails. For example, each customer receiving Internet Protocol Television (“IPTV”) may be assigned two content servers. If the first content server fails, the second content server may continue to provide IPTV to the customer. In this case, each content server may be connected to multiple customers. Thus, each content server may provide IPTV to more than one customer.
The above-described configurations of monitors/edge routers and content servers/customer may be illustrated as a graph under conventional graph theory. In particular, each monitor and each content server may be represented as a covering node, and each edge router and each customer may be represented to as a branch node. In one scenario, a user may be provided a topology that includes multiple covering nodes, multiple branch nodes, and a multiple edges connecting the covering nodes and the branch nodes. Under the so-called covering-by-pairs problem, the service provider selects the covering nodes at a minimum cost such that the branch nodes are covered. A branch node is considered covered if it is connected to two of the covering nodes. The minimum cost may be determined by a variety of criteria, such as a minimum number of covering nodes or a minimum weight of covering nodes.
A basic solution to the covering-by-pairs problem is to simply traverse each branch node and randomly select pairs of covering nodes such that the branch nodes are covered. While this solution may be the easiest, it is generally considered sub-optimal because it does not account for the cost of the covering nodes. For example, this solution may result in each branch node being covered by two independent covering nodes. This type of result can be cost-prohibitive, especially if the covering nodes are relatively expensive. For example, IP traffic monitors and content servers as described above are generally expensive components to purchase, deploy, operate, and maintain.